# -*- coding: utf-8 -*-
"""
Created on Sat Aug 31 14:47:03 2019

@author: Administrator
"""

def merge_sort(temp_list):
    
    length = len(temp_list)
    
    middle = length // 2
    
    one_length = len(temp_list[0:middle])
    another_length = len(temp_list[middle:])
    
    if one_length <= 1 and another_length <= 1:
        result = merge(temp_list[0:middle], temp_list[middle:])
    
    else:
        half = merge_sort(temp_list[0:middle]) 
        another_half = merge_sort(temp_list[middle:])
        
        # 出现问题：如何保证合并后也是有序的
        result = merge(half, another_half)
    
    return result

def merge(one, another):
    
    # 使用插入排序，以大的list为底，用小的list去插入到大的list中
    inserted = []
    insertor = []
    
    if one >= another:
        inserted = one
        insertor = another
    else:
        inserted = another
        insertor = one
    
    # 插入法
    for ele in insertor:
        for i in range(len(inserted)):
            if inserted[i] >= ele:
                inserted.insert(i, ele)
                break

    return inserted

#one = []
#another = []
#print(merge(one, another))

start = [3, 1, 2, 8, 7, 5, 9, 4, 0, 6]
print(merge_sort(start))